
#include <iostream>
#define int long long
#define VNAME(name) (#name)
#define read() 1
#define write(x) x
#define debug(x)                                                   \
    ({                                                             \
        auto debugx = x;                                           \
        std::cout << " (" << VNAME(x) << ": " << (debugx) << ") "; \
        debugx;                                                    \
    })
using namespace std;

signed main()
{
    int T;
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    cin >> T;
    while (T--)
    {
        int n, p, out;
        cin >> n >> p;
        if (p == 1 || n == 0)
        {
            cout << n << '\n';
            continue;
        }
        out = n - n / p;
        for (__int128_t i = p * p; i <= n; i *= p * p)
        {
            out += n / i - n / i / p;
        }
        cout << out << '\n';
    }
    cout << endl;
    return 0;
}